package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import zcw.com.lib_leet_code.bean.TreeNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2019/7/5.<br><br>
 *
 * 二叉树的后序遍历
 */
public class Topic145 {

    public static void main(String[] args) {
        Topic145 instance = new Topic145();

        List<Integer> list = Arrays.asList(1, null, 2, null, null, 3);
        TreeNode root = Util.createTree(list);
        System.out.println(instance.postorderTraversal(root));

        list = Arrays.asList();
        root = Util.createTree(list);
        System.out.println(instance.postorderTraversal(root));

        list = Arrays.asList(1);
        root = Util.createTree(list);
        System.out.println(instance.postorderTraversal(root));

        list = Arrays.asList(1, 2);
        root = Util.createTree(list);
        System.out.println(instance.postorderTraversal(root));

        list = Arrays.asList(1, null, 2);
        root = Util.createTree(list);
        System.out.println(instance.postorderTraversal(root));
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        List<TreeNode> stack = new ArrayList<>();

        while (root != null || stack.size() > 0) {
            while (root != null) {
                stack.add(root);
                root = root.left;
            }

            TreeNode node = stack.get(stack.size() - 1).right;
            if(node == null) {
                node = stack.remove(stack.size() - 1);
                result.add(node.val);

                while(stack.size() > 0 && stack.get(stack.size() - 1).right == node) {
                    node = stack.remove(stack.size() - 1);
                    result.add(node.val);
                }
            }
            else {
                root = node;
            }
        }

        return result;
    }

    public List<Integer> postorderTraversal3(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        List<TreeNode> stack = new ArrayList<>();

        while (root != null || stack.size() > 0) {
            while (root != null) {
                stack.add(root);
                result.add(0, root.val);
                root = root.right;
            }

            root = stack.remove(stack.size() - 1);
            root = root.left;
        }

        return result;
    }

    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorderTraversal(root, result);
        return result;
    }

    private void postorderTraversal(TreeNode root, List<Integer> result) {
        if(root == null || result == null) {
            return ;
        }

        postorderTraversal(root.left, result);
        postorderTraversal(root.right, result);
        result.add(root.val);
    }
}
